package de.haw.gka.a1;

import java.util.*;

import org.jgrapht.alg.util.UnionFind;
import org.jgrapht.graph.AbstractGraph;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.WeightedPseudograph;

public class AlgoKruskal extends AbstractSearchAlgo{

    private AbstractGraph<Knoten, DefaultWeightedEdge> graph;
	private WeightedPseudograph<Knoten, DefaultWeightedEdge> miniGraph;
	private int gewicht =0;

	public AlgoKruskal(AbstractGraph<Knoten, DefaultWeightedEdge> graph){
		this.graph=graph;
		algo();
	}
	
	private void algo(){

        miniGraph= new WeightedPseudograph<Knoten, DefaultWeightedEdge>(DefaultWeightedEdge.class);
		List<DefaultWeightedEdge> sortiertKanten = new ArrayList<DefaultWeightedEdge>(graph.edgeSet());
		Collections.sort(sortiertKanten,new KantenComp(graph));
		UnionFind<Knoten> unionF= new UnionFind<Knoten>(graph.vertexSet());
		while(!sortiertKanten.isEmpty() && miniGraph.vertexSet().size() < graph.vertexSet().size()){
			DefaultWeightedEdge kante= sortiertKanten.get(0);
			Knoten von = graph.getEdgeSource(kante);
			Knoten zu= graph.getEdgeTarget(kante);
			miniGraph.addVertex(von);
			miniGraph.addVertex(zu);
			sortiertKanten.remove(0);
			if (!(unionF.find(von).equals(unionF.find(zu)))){
				unionF.union(von, zu);
				miniGraph.addEdge(von, zu);
				gewicht+=graph.getEdgeWeight(kante);
			}
		}
	}
	public int getGewicht(){
		return gewicht;
	}
	
	public WeightedPseudograph<Knoten, DefaultWeightedEdge> getMiniGraph(){
		return miniGraph;
	}
	@Override
	public List getTheShortestWay() {
		 List tmp = new ArrayList();
	     tmp.addAll(miniGraph.edgeSet());
	     return tmp;
	}
	
	private class KantenComp implements Comparator<DefaultWeightedEdge>{
		
		private AbstractGraph<Knoten, DefaultWeightedEdge> graph;
		public KantenComp(AbstractGraph<Knoten, DefaultWeightedEdge> graph){
			this.graph=graph;
		}
		
		@Override 
		public int compare(DefaultWeightedEdge k1, DefaultWeightedEdge k2) {
			Double kante1 = graph.getEdgeWeight(k1);
			Double kante2 = graph.getEdgeWeight(k2);
			return kante1.compareTo(kante2);
		}
	}


	
	
	
}
